using System;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0343. 整数拆分")]
    public class No0343_IntegerBreak : AbsBaseTestItem
    {
        /*
        给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
        */
        public override void OnTest()
        {
            Assert.TestExe(IntegerBreak, 2, 1);
            Assert.TestExe(IntegerBreak, 10, 36);

            Assert.TestExe(IntegerBreak_2, 2, 1);
            Assert.TestExe(IntegerBreak_2, 10, 36);

            Assert.TestExe(IntegerBreak_3, 2, 1);
            Assert.TestExe(IntegerBreak_3, 10, 36);

            Assert.TestExe(IntegerBreak_4, 2, 1);
            Assert.TestExe(IntegerBreak_4, 10, 36);
        }

        /// <summary>
        /// 方法一：动态规划
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public int IntegerBreak(int n)
        {
            int[] dp = new int[n + 1];
            for (int i = 2; i <= n; i++)
            {
                int curMax = 0;
                for (int j = 1; j < i; j++)
                {
                    int max = Math.Max(j * (i - j), j * dp[i - j]);
                    curMax = Math.Max(curMax, max);
                }
                dp[i] = curMax;
            }
            return dp[n];
        }

        /// <summary>
        /// 方法二：优化的动态规划
        /// </summary>
        public int IntegerBreak_2(int n)
        {
            if (n < 4)
            {
                return n - 1;
            }
            int[] dp = new int[n + 1];
            dp[2] = 1;
            for (int i = 3; i <= n; i++)
            {
                dp[i] = Math.Max(Math.Max(2 * (i - 2), 2 * dp[i - 2]), Math.Max(3 * (i - 3), 3 * dp[i - 3]));
            }
            return dp[n];
        }

        /// <summary>
        /// 方法三：数学
        /// </summary>
        public int IntegerBreak_3(int n)
        {
            if (n <= 3)
            {
                return n - 1;
            }
            int quotient = n / 3;
            int remainder = n % 3;
            if (remainder == 0)
            {
                return (int)Math.Pow(3, quotient);
            }
            else if (remainder == 1)
            {
                return (int)Math.Pow(3, quotient - 1) * 4;
            }
            else
            {
                return (int)Math.Pow(3, quotient) * 2;
            }
        }

        /// <summary>
        /// 评论人员: 为了亿 的算法
        /// </summary>
        public int IntegerBreak_4(int n)
        {
            if (n <= 3)
                return n - 1;
            int ans = 1;
            while (n > 4)
            {
                ans *= 3;
                n -= 3;
            }
            return ans * n;
        }
    }
}
